package se.webbzon.oschi01.metric;

public final class XWangMetric implements Metric<String> {
	
	private final boolean caseSensitive;
	
	public XWangMetric() {
		this(true);
	}
	
	public XWangMetric(boolean caseSensitive) {
		this.caseSensitive = caseSensitive;
	}

	@Override public double distance(String lhs, String rhs) {
		int len1 = lhs.length();
		int len2 = rhs.length();
	 
		// len1+1, len2+1, because finally return dp[len1][len2]
		int[][] dp = new int[len1 + 1][len2 + 1];
	 
		for (int i = 0; i <= len1; i++) {
			dp[i][0] = i;
		}
	 
		for (int j = 0; j <= len2; j++) {
			dp[0][j] = j;
		}
	 
		//iterate though, and check last char
		for (int i = 0; i < len1; i++) {
			char c1 = lhs.charAt(i);
			for (int j = 0; j < len2; j++) {
				char c2 = rhs.charAt(j);
	 
				//if last two chars equal
				if (equals(c1,c2)) {
					//update dp value for +1 length
					dp[i + 1][j + 1] = dp[i][j];
				} else {
					int replace = dp[i][j] + 1;
					int insert = dp[i][j + 1] + 1;
					int delete = dp[i + 1][j] + 1;
	 
					int min = replace > insert ? insert : replace;
					min = delete > min ? min : delete;
					dp[i + 1][j + 1] = min;
				}
			}
		}
	 
		return  1.0 - (1.0 / (1.0 + dp[len1][len2]));
	}
	
	private final boolean equals(char lhs, char rhs) {
		if (caseSensitive)
			return lhs == rhs;
		else
			return Character.toLowerCase(lhs) == Character.toLowerCase(rhs);
	}

}
